﻿import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

import JEightTeam.*;

public class PrintShortestPaths {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		/*
		Scanner in = new Scanner(System.in);
		String inputLine = in.nextLine();
		String[] strs = inputLine.split(" ");
		
		int v_num = Integer.parseInt(strs[0]);
		int e_num = Integer.parseInt(strs[1]);
		
		int[][] udg = new int[v_num+1][v_num+1];
		
		//将顶点间的距离初始化为很大的值，相当于这两点之间无连接
		for(int i=1; i<=v_num; i++){
			for(int j=1; j<=v_num; j++){
				udg[i][j] = 1000;
			}
		}
		
		int start_v, end_v, weight;
		
		//输入边的信息
		while(e_num>0){
			inputLine = in.nextLine();
			strs = inputLine.split(" ");
			if(strs.length == 3){
				start_v = Integer.parseInt(strs[0]);
				end_v = Integer.parseInt(strs[1]);
				weight = Integer.parseInt(strs[2]);
				//无向图是对称的，所以一条边的长度在矩阵中需要输入两次
				udg[start_v][end_v] = weight;
				udg[end_v][start_v] = weight;
				e_num--;
			}
			else{
				System.out.println("输入的数据不正确");
			}
		}
		
		//输入开始和结束顶点编号
		inputLine = in.nextLine();
		strs = inputLine.split(" ");
		
		start_v = Integer.parseInt(strs[0]);
		end_v = Integer.parseInt(strs[1]);

		//调用自定义函数，输出相关的信息
		ShortestPath(start_v, end_v, udg);
		*/
		
		try{
			//使用IO文本文件输入数据
			TextReaderExt reader = new TextReaderExt();
			//reader.PrintGrapharr();
			int[][] arr = reader.getGraphArr();
			
			/*找到最短路径长度*/
			int[] arrTmp = JEightTeam.DijkstraArr.Dijsktra(arr, reader.getStartVertex()-1);
			int shortestD = arrTmp[reader.getEndVertex() - 1];
			
			/*找到起点和终点之间的所有路径*/
			/* 定义节点数组 */  
			int len = reader.getVertexNum();
			int[][] tmp = reader.getGraphArr();
			int[][] nodeRelation = new int[len][len];
			for(int i=0;i<len;i++){
				for(int j=0;j<len;j++){
					nodeRelation[i][j] = -1;
				 }
			 }

			for(int i=0;i<len;i++){
				for(int j=0;j<len;j++){
					if(tmp[i][j] != TextReaderExt.Max)
						nodeRelation[i][j] = j;
				 }
			 }
			 
			//int len = nodeRalation.length;
			Node[] node = new Node[len];
			for(int i=0;i<len;i++){
				node[i] = new Node();  
			    node[i].setName(i);  
			  } 
			/* 定义与节点相关联的节点集合 */
			int iTmp;
			for(int i=0;i<len;i++){
				ArrayList<Node> List = new ArrayList<Node>();					
				for(int j=0;j<nodeRelation[i].length;j++){
					//System.out.println(i + "--" + j);
					if(nodeRelation[i][j] != -1){
						iTmp = nodeRelation[i][j];
						List.add(node[iTmp]);
					}
			           }  
				node[i].setRelationNodes(List);  
				List = null;  //释放内存  
			 }
			/* 开始搜索所有路径 */  
			//MGraphSearch.gArr = tmp;
			MGraphSearch.shortestD = shortestD;
			MGraphSearch.getPaths(node[1], null, node[1], node[3]);
			
			ArrayList<Object[]>  path = MGraphSearch.sers;
			Iterator<Object[]> it = path.iterator();
			Object[] nArr;
			int pathLen=0,row=0,col=0,c=0,d=0;
			//使用IO文本文件输入数据
			TextReaderExt reader1 = new TextReaderExt();
			int[][] gArr = reader1.getGraphArr();
			ArrayList<Object[]> result = new ArrayList<Object[]>();
			while(it.hasNext()){
				nArr = it.next();
				c++;
				for(int i=0;i<nArr.length;i++){
					if(i != 0){
						row = ((Node)nArr[i-1]).getName();
						col = ((Node)nArr[i]).getName();
						pathLen += gArr[row][col];
					}
				}
				if(pathLen == shortestD){
					result.add(nArr);
				}
				//System.out.println(pathLen);
				pathLen = 0;
			}
			Iterator<Object[]> it1 = result.iterator();
			Object[] oArr;
			System.out.println("###########################################");
			System.out.println("最短路径个数：" + result.size() + ",最短路径为："  + shortestD);
			while(it1.hasNext()){
				oArr = it1.next();
				for (int i = 0; i < oArr.length; i++) {
					Node nNode = (Node) oArr[i];	
					if(i < (oArr.length - 1))  
						System.out.print((nNode.getName()+1) + "->");  
					else  
						System.out.print(nNode.getName()+1);  
			        }  
				System.out.println();
			}
			/*deal.ArrTranToGraphAdjList();
			JEightTeam.GraphAdjList g = deal.getGraphAdjList();
			//g.GraphAdjListPrint();
			//DijkstraStart
			//(int vNum,int s,int e,GraphAdjList g)
			System.out.println(g.vertexeNum);
			System.out.println(reader.getStartVertex());
			System.out.println(reader.getEndVertex());
			DijkstraExt di = new DijkstraExt(g.vertexeNum,reader.getStartVertex(),reader.getEndVertex(),g);
			int i = di.DijkstraStart();
			System.out.println("the shortest distance is:" + i);
			*/
		}
		catch(Exception e){
			System.out.println(e.getStackTrace());
		}
	}
	
	public static void ShortestPath(int vstart, int vend, int[][] graph){
		
		System.out.println("ShortestPath");
		//确定最小的路径长度，并将该值赋给shortest_weight
		 
		//选出和最小路径长度一样的几条路径，专门放到Path List里
		 
		//对所有的结果进行竖向的排序
		 

		//输出计算结果
	}
	
	//判断需要加入的点是否在已有的路径中
	public static boolean isNotInArray(int num, int[] arr){
		for(int i=0; i<arr.length; i++){
			if(num == arr[i])
				return false;
		}
		return true;
	}
	
	//将前面不为0的点按照编号反转
	public static void partInverse(int[] arr){
		int i;
		for(i=0; i<arr.length; ){
			if(arr[i]>0)
				i++;
		}

		for(int j=0; j<=(i-1)/2; j++){
			int temp = arr[j];
			arr[j] = arr[i-j-1];
			arr[i-j-1]=temp;
		}
	}
}

//定义路径类，里面包含当前路径从初点到终点的距离distance
//从始点到终点经过的点数num_of_over，如点1通过2,4到5，那么distance存储的是始点到终点的距离
//num_of_over存储的是3（即经过2,4,5三点才到终点），route中存储的是1 2 4 5这四个数值
class Path{
	int distance;
	int num_of_over;
	int[] route;
}

